package _76

import (
	. "GoLeetcode/common"
)

/*
时间复杂度：O(N)
空间复杂度：O(N)

逆向动态规划
*/

func mostPoints(questions [][]int) int64 {
	n := len(questions)
	dp := make([]int64, n+1)
	for i := n - 1; i >= 0; i-- {
		pre := i + questions[i][1] + 1
		if pre > n {
			dp[i] = MaxInt64(dp[i+1], int64(questions[i][0]))
		} else {
			dp[i] = MaxInt64(dp[i+1], dp[pre]+int64(questions[i][0]))
		}
	}
	return dp[0]
}
